package com.breeze.leetcode;

/**
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 * 121. 买卖股票的最佳时机
 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
 * <p>
 * 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
 * <p>
 * 注意：你不能在买入股票前卖出股票。
 * <p>
 */
public class LeetCode121 {
    // f(i) = max(f(i-1),prices[i]-(i-1的最小值))

    /**
     * 1. 动态规划
     * 状态转移方程：dp[i]=max(dp[i−1],prices[i]−minprice)
     * 边界条件： dp[0]=0
     * <p>
     * 我们可以使用prices数组代替dp数组，对于minprice用一个变量维护即可
     * <p>
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int minPrice = prices[0];
        for (int i = 0; i < prices.length; i++) {
            // 边界条件
            if (i == 0) {
                prices[0] = 0;
                continue;
            }
            // 更新minPrice
            minPrice = Math.min(minPrice, prices[i]);
            // 状态转移
            prices[i] = Math.max(prices[i - 1], prices[i] - minPrice);
        }
        return prices[prices.length - 1];
    }

    /**
     * 2. 迭代法
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * 虽然和动态规划时间复杂度和空间复杂度处于同一量级，但显然该方法处理简单
     */
    public int maxProfit1(int[] prices) {
        int maxProfit = 0;
        int minPrice = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        LeetCode121 leetCode121 = new LeetCode121();
        int[] prices1 = {7, 1, 5, 3, 6, 4}; // 5
        int[] prices2 = {7, 6, 4, 3, 1}; //0
        int[] prices3 = {2, 4, 1}; //2
        int[] prices4 = {}; //0
        int maxProfit1 = leetCode121.maxProfit1(prices1);
        int maxProfit2 = leetCode121.maxProfit1(prices2);
        int maxProfit3 = leetCode121.maxProfit1(prices3);
        int maxProfit4 = leetCode121.maxProfit1(prices4);
        System.out.println(maxProfit1);
        System.out.println(maxProfit2);
        System.out.println(maxProfit3);
        System.out.println(maxProfit4);
    }
}
